package nachos.threads;

import nachos.machine.*;

import java.util.LinkedList;

/**
 * KThread 是一个可用于执行 Nachos 内核代码的线程
 * Nachos 允许多个线程同时运行
 * <p>
 * 要创建一个新线程，首先要声明一个实现 Runnable 接口的类，并且该类实现了 run 方法
 * 然后该类的实例就可以被分配、创建 KThread 时作为参数传递、fork
 * 例如，计算 π 的线程可以按如下方式写
 *
 * <p><blockquote><pre>
 * class PiRun implements Runnable {
 *     public void run() {
 *         // compute pi
 *         ...
 *     }
 * }
 * </pre></blockquote>
 * <p>然后，以下代码将创建一个线程并开始让它运行：
 *
 * <p><blockquote><pre>
 * PiRun p = new PiRun();
 * new KThread(p).fork();
 * </pre></blockquote>
 */
public class KThread {
    /**
     * 获取当前线程
     *
     * @return 当前线程
     */
    public static KThread currentThread() {
        Lib.assertTrue(currentThread != null);
        return currentThread;
    }

    /**
     * 分配一个新的 KThread，如果这是第一个 Thread，创建一个空闲线程
     */
    public KThread() {
        if (currentThread != null) {
            tcb = new TCB();
        } else {
            // 参数表示是否允许优先级传递
            readyQueue = ThreadedKernel.scheduler.newThreadQueue(true);
            readyQueue.acquire(this);

            currentThread = this;
            tcb = TCB.currentTCB();
            name = "main";
            restoreState();

            createIdleThread();
        }

        // 初始化等待线程列表
        waitThreadList = new LinkedList<>();
    }

    /**
     * 声明一个新的 KThread.
     *
     * @param target 调用其 run 方法的对象
     */
    public KThread(Runnable target) {
        this();
        this.target = target;
    }

    /**
     * 设置该线程的 target
     *
     * @param target run() 方法要被调用的对象
     * @return 该线程
     */
    public KThread setTarget(Runnable target) {
        Lib.assertTrue(status == statusNew);

        this.target = target;
        return this;
    }

    /**
     * 设置该线程的名称
     * 名称仅用于调试的目的
     *
     * @param name 要给该线程的名称
     * @return 该线程
     */
    public KThread setName(String name) {
        this.name = name;
        return this;
    }

    /**
     * 获取该线程的名称
     * 名称仅用于调试的目的
     *
     * @return 这个线程的名称
     */
    public String getName() {
        return name;
    }

    /**
     * 获取此线程的完整名称
     * 完整名称包括它的名称以及数字 ID
     * 名称仅用于调试的目的
     *
     * @return 线程的完整名称
     */
    public String toString() {
        return (name + " (#" + id + ")");
    }

    /**
     * 确定且一致地将此线程与另一个线程进行比较
     */
    public int compareTo(Object o) {
        KThread thread = (KThread) o;

        if (id < thread.id)
            return -1;
        else if (id > thread.id)
            return 1;
        else
            return 0;
    }

    /**
     * 使这个线程开始执行
     * 结果是两个线程同时进行：
     * 当前进程（从调用 fork 方法返回的进程）、另一个进程（执行它的 target 的 run 方法）
     */
    public void fork() {
        Lib.assertTrue(status == statusNew);
        Lib.assertTrue(target != null);

        Lib.debug(dbgThread, "Forking thread: " + toString() + " Runnable: " + target);

        boolean intStatus = Machine.interrupt().disable();

        tcb.start(new Runnable() {
            public void run() {
                runThread();
            }
        });

        ready();

        Machine.interrupt().restore(intStatus);
    }

    private void runThread() {
        begin();
        target.run();
        finish();
    }

    private void begin() {
        Lib.debug(dbgThread, "Beginning thread: " + toString());

        Lib.assertTrue(this == currentThread);

        restoreState();

        Machine.interrupt().enable();
    }

    /**
     * 完成当前线程，并计划在安全的情况下销毁它
     * 当线程的 run 方法返回时，会自动调用此方法，但也可以直接调用
     * <p>
     * 当前线程无法立即销毁，因为它的栈和其他执行状态仍在使用中
     * 相反，在能安全删除该线程的情况下，这个线程会被下一个要运行的的线程自动销毁
     */
    public static void finish() {
        Lib.debug(dbgThread, "Finishing thread: " + currentThread.toString());

        Machine.interrupt().disable();

        Machine.autoGrader().finishingCurrentThread();

        Lib.assertTrue(toBeDestroyed == null);

        toBeDestroyed = currentThread;
        currentThread.status = statusFinished;

        // 遍历当前线程的等待线程列表
        for (KThread waitThread : currentThread().waitThreadList) {
            // 让等待线程进入就绪装填
            waitThread.ready();
        }

        sleep();
    }

    /**
     * 如果任何其他线程准备运行，则放弃 CPU
     * 如果是这样，请将当前线程放在就绪队列上，以便最终对其进行重新排序
     *
     * <p>
     * 如果没有其他线程准备运行，则立即返回
     * 否则，在当前线程被 readyQueue.nextThread() 选择再次运行的时候返回
     *
     * <p>
     * 中断被关闭，因此当前线程可以自动将自己添加到就绪队列并切换到下一个线程
     * 返回时，如果在关中断的情况下调用 yield()，则将中断恢复到以前的状态
     */
    public static void yield() {
        Lib.debug(dbgThread, "Yielding thread: " + currentThread.toString());

        Lib.assertTrue(currentThread.status == statusRunning);

        boolean intStatus = Machine.interrupt().disable();

        currentThread.ready();

        runNextThread();

        Machine.interrupt().restore(intStatus);
    }

    /**
     * 放弃 CPU，因为当前线程已完成或被阻塞
     * 此线程必须是当前线程
     *
     * <p>
     * 如果当前线程被阻塞（信号量、锁、条件变量），最终某个线程将唤醒该线程，将其放回就绪队列并重新调度
     * 否则，finish() 应该计划由下一个要运行的线程销毁此线程
     */
    public static void sleep() {
        Lib.debug(dbgThread, "Sleeping thread: " + currentThread.toString());

        Lib.assertTrue(Machine.interrupt().disabled());

        if (currentThread.status != statusFinished)
            currentThread.status = statusBlocked;

        runNextThread();
    }

    /**
     * 将此线程移动到就绪状态，并将其添加到调度程序的就绪队列中
     */
    public void ready() {
        Lib.debug(dbgThread, "Ready thread: " + toString());

        Lib.assertTrue(Machine.interrupt().disabled());
        Lib.assertTrue(status != statusReady);

        status = statusReady;
        if (this != idleThread)
            readyQueue.waitForAccess(this);

        Machine.autoGrader().readyThread(this);
    }

    /**
     * 等待该线程完成：
     * 如果该线程已经完成了，立即返回
     * 此方法只能调用一次，第二次调用不能保证返回
     * 该线程不能是当前不能是当前线程
     */
    public void join() {
        Lib.debug(dbgThread, "Joining to thread: " + toString());

        Lib.assertTrue(this != currentThread);

        // 关中断，同时获取到之前的中断状态
        boolean intStatus = Machine.interrupt().disable();

        // 使之前的优先级顺序失效
        this.setPriorityStatus(false);

        // 如果该线程（调用 join 方法的线程）未处于完成状态
        if (this.status != statusFinished) {
            // 将当前线程（正在运行的线程）添加到等待线程列表
            waitThreadList.add(KThread.currentThread());
            // 让当前线程进入休眠状态
            currentThread.sleep();
        }

        // 恢复中断
        Machine.interrupt().restore(intStatus);
    }

    // 等待线程列表（在构造方法中进行初始化）
    private LinkedList<KThread> waitThreadList = null;

    // 获取等待线程列表
    public LinkedList<KThread> getWaitThreadList() {
        return waitThreadList;
    }

    /**
     * 创建空间线程
     * 每当没有线程准备运行，并且调用了 runnexthread() 时，它将运行空闲线程
     * 空闲线程决不能阻塞，只有当所有其他线程都被阻塞时，才允许它运行
     *
     * <p>
     * 请注意，ready() 从不将空闲线程添加到就绪集合
     */
    private static void createIdleThread() {
        Lib.assertTrue(idleThread == null);

        idleThread = new KThread(new Runnable() {
            public void run() {
                while (true) yield();
            }
        });
        idleThread.setName("idle");

        Machine.autoGrader().setIdleThread(idleThread);

        idleThread.fork();
    }

    /**
     * 确定要运行的下一个线程，然后将 CPU 分配给使用 run() 的线程
     */
    private static void runNextThread() {
        KThread nextThread = readyQueue.nextThread();
        if (nextThread == null)
            nextThread = idleThread;

        nextThread.run();
    }

    /**
     * 将 CPU 分配到此线程
     * 保存当前线程的状态，通过调用 TCB.contextSwitch() 切换到新线程，然后载入新线程的状态。
     * 新线程将成为当前线程
     *
     * <p>
     * 如果新线程和旧线程相同，该方法必须仍调用 saveState()、contextSwitch() 和 restoreState()
     *
     * <p>
     * 先前运行的线程必须从 running 转到 blocked 或 ready（取决于该线程是要休眠还是让步）
     *
     * @param finishing 如果当前线程已完成且应该被新线程销毁，该值为 true
     */
    private void run() {
        Lib.assertTrue(Machine.interrupt().disabled());

        Machine.yield();

        currentThread.saveState();

        Lib.debug(dbgThread, "Switching from: " + currentThread.toString()
                + " to: " + toString());

        currentThread = this;

        tcb.contextSwitch();

        currentThread.restoreState();
    }

    /**
     * 准备要运行的线程
     * 将 status 设置为 statusRunning，并检查 toBeDestroyed
     */
    protected void restoreState() {
        Lib.debug(dbgThread, "Running thread: " + currentThread.toString());

        Lib.assertTrue(Machine.interrupt().disabled());
        Lib.assertTrue(this == currentThread);
        Lib.assertTrue(tcb == TCB.currentTCB());

        Machine.autoGrader().runningThread(this);

        status = statusRunning;

        if (toBeDestroyed != null) {
            toBeDestroyed.tcb.destroy();
            toBeDestroyed.tcb = null;
            toBeDestroyed = null;
        }
    }

    /**
     * 准备此线程来放弃处理器
     * 内核线程不需要在此处执行任何操作
     */
    protected void saveState() {
        Lib.assertTrue(Machine.interrupt().disabled());
        Lib.assertTrue(this == currentThread);
    }

    private static class PingTest implements Runnable {
        PingTest(int which) {
            this.which = which;
        }

        public void run() {
            for (int i = 0; i < 5; i++) {
                System.out.println("*** thread " + which + " looped "
                        + i + " times");
                currentThread.yield();
            }
        }

        private int which;
    }

    public static void test1() {
        System.out.println("\n<--- 题目 1 开始测试 --->\n");

        // 创建 A 线程
        KThread threadA = new KThread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 5; i++) {
                    // 如果就绪队列中有其他线程，那么该线程让出 CPU，进入就绪队列
                    System.out.println("A 线程尝试让出 CPU");
                    currentThread.yield();
                }
                System.out.println("A 线程运行结束");
            }
        });

        // 创建 B 线程
        KThread threadB = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("B 线程开始运行");
                // A 线程加入
                System.out.println("A 线程加入");
                threadA.join();
                System.out.println("B 线程结束运行");
                // 要在两个线程都结束的时候打印下面语句
                System.out.println("\n<--- 题目 1 结束测试 --->\n");
            }
        });

        // 启动线程
        threadB.fork();
        threadA.fork();
    }

    public static void test2() {
        System.out.println("\n<--- 题目 2 开始测试 --->\n");

        // 创建锁以及条件变量
        Lock lock = new Lock();
        Condition2 condition = new Condition2(lock);

        // 创建 A 线程
        KThread threadA = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("A 线程开始运行");
                // 获得锁
                lock.acquire();
                // 挂起当前线程
                System.out.println("A 线程进入休眠状态");
                condition.sleep();
                System.out.println("A 线程被唤醒");
                // 释放锁
                lock.release();
                System.out.println("A 线程结束运行");
            }
        });

        // 创建 B 线程
        KThread threadB = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("B 线程开始运行");
                // 获得锁
                lock.acquire();
                // 挂起当前线程
                System.out.println("B 线程进入休眠状态");
                condition.sleep();
                System.out.println("B 线程被唤醒");
                // 释放锁
                lock.release();
                System.out.println("B 线程结束运行");
                System.out.println("\n<--- 题目 2 结束测试 --->\n");
            }
        });

        // 创建 C 线程
        KThread threadC = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("C 线程开始运行");
                // 获得锁
                lock.acquire();
                // 唤醒所有线程
                System.out.println("C 线程尝试唤醒所有线程");
                condition.wakeAll();
                // 释放锁
                lock.release();
                System.out.println("C 线程结束运行");
            }
        });

        // 启动线程
        threadA.fork();
        threadB.fork();
        threadC.fork();
    }

    public static void test3() {
        System.out.println("\n<--- 题目 3 开始测试 --->\n");

        // 创建 A 进程
        KThread threadA = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("A 线程开始运行");
                // 等待时间以及计算最早唤醒时刻
                long waitTime = 100;
                long earliestWakeTime = waitTime + Machine.timer().getTime();
                System.out.println("A 线程将要休眠，最早唤醒时刻：" + earliestWakeTime);
                // 让线程 A 进入休眠状态
                ThreadedKernel.alarm.waitUntil(waitTime);
                // 实际唤醒时刻以及与最早唤醒时刻的差值
                long actualWakeTime = Machine.timer().getTime();
                System.out.println("A 线程退出休眠，实际唤醒时刻：" + actualWakeTime);
                System.out.println("A 线程两时刻差值：" + (actualWakeTime - earliestWakeTime));
            }
        });

        // 创建 B 进程
        KThread threadB = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("B 线程开始运行");
                // 等待时间以及计算最早唤醒时刻
                long waitTime = 1000;
                long earliestWakeTime = waitTime + Machine.timer().getTime();
                System.out.println("B 线程将要休眠，最早唤醒时刻：" + earliestWakeTime);
                // 让线程 A 进入休眠状态
                ThreadedKernel.alarm.waitUntil(waitTime);
                // 实际唤醒时刻以及与最早唤醒时刻的差值
                long actualWakeTime = Machine.timer().getTime();
                System.out.println("B 线程退出休眠，实际唤醒时刻：" + actualWakeTime);
                System.out.println("B 线程两时刻差值：" + (actualWakeTime - earliestWakeTime));

                System.out.println("\n<--- 题目 3 结束测试 --->\n");
            }
        });

        // 启动线程
        threadA.fork();
        threadB.fork();
    }

    public static void test4() {
        System.out.println("\n<--- 题目 4 开始测试 --->\n");

        Communicator communicator = new Communicator();

        // 创建 A 进程
        KThread threadA = new KThread(new Runnable() {
            @Override
            public void run() {
                // A 线程不断发送信息
                for (int i = 0; i < 5; i++) {
                    System.out.println("A 线程说：" + (i + 1));
                    communicator.speak(i + 1);
                }
            }
        });

        // 创建 B 进程
        KThread threadB = new KThread(new Runnable() {
            @Override
            public void run() {
                // B 线程不断接收信息
                for (int i = 0; i < 5; i++) {
                    System.out.println("B 线程准备听");
                    int word = communicator.listen();
                    System.out.println("B 线程听到了：" + word);
                }

                System.out.println("\n<--- 题目 4 结束测试 --->\n");
            }
        });

        // 启动线程
        threadA.fork();
        threadB.fork();
    }

    public static void test5() {
        System.out.println("\n<--- 题目 5 开始测试 --->\n");

        PriorityScheduler scheduler = new PriorityScheduler();

        KThread threadA = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("A 线程开始运行，初始优先级为 2");
                System.out.println("A 线程尝试让出 CPU");
                yield();
                System.out.println("A 线程重新使用 CPU");
                System.out.println("A 线程结束运行");
            }
        });

        KThread threadB = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("B 线程开始运行，初始优先级为 4");
                System.out.println("B 线程尝试让出 CPU");
                yield();
                System.out.println("B 线程重新使用 CPU");
                System.out.println("B 线程结束运行");

                // 允许优先级传递时打印下面的语句
                System.out.println("\n<--- 题目 5 结束测试 --->\n");
            }
        });

        KThread threadC = new KThread(new Runnable() {
            @Override
            public void run() {
                System.out.println("C 线程开始运行，初始优先级为 6");
                System.out.println("C 线程尝试让出 CPU");
                yield();
                System.out.println("C 线程重新使用 CPU");
                System.out.println("C 线程等待 A 线程");
                threadA.join();
                System.out.println("C 线程重新使用 CPU");
                System.out.println("C 线程结束运行");

//                // 不允许优先级传递时打印下面的语句
//                System.out.println("\n<--- 题目 5 结束测试 --->\n");
            }
        });


        scheduler.getThreadState(threadA).setPriority(2);
        scheduler.getThreadState(threadB).setPriority(4);
        scheduler.getThreadState(threadC).setPriority(6);

        threadA.fork();
        threadB.fork();
        threadC.fork();
    }

    public static void test6() {
        Boat.selfTest();
    }

    /**
     * 测试此模块是否正常工作
     */
    public static void selfTest() {
        Lib.debug(dbgThread, "Enter KThread.selfTest");

        // 调用测试程序
//        test5();
    }

    private static final char dbgThread = 't';

    /**
     * 调度程序的附加状态
     *
     * @see nachos.threads.PriorityScheduler.ThreadState
     */
    public Object schedulingState = null;

    private static final int statusNew = 0;
    private static final int statusReady = 1;
    private static final int statusRunning = 2;
    private static final int statusBlocked = 3;
    private static final int statusFinished = 4;

    /**
     * 此线程的状态：
     * new（未 fork）、ready（在就绪队列但未运行）、running、blocked（不在就绪队列，也没在运行）
     */
    private int status = statusNew;
    private String name = "(unnamed thread)";
    private Runnable target;
    private TCB tcb;

    /**
     * 此线程的唯一标识符，用于确定性地比较线程
     */
    private int id = numCreated++;
    /**
     * 调用 KThread 构造函数的次数
     */
    private static int numCreated = 0;

    private static ThreadQueue readyQueue = null;
    private static KThread currentThread = null;
    private static KThread toBeDestroyed = null;
    private static KThread idleThread = null;

    // 优先级状态：之前的优先级顺序是否有效，true 表示有效
    private static boolean priorityStatus = false;

    // 获取优先级状态
    public static boolean getPriorityStatus() {
        return priorityStatus;
    }

    // 改变优先级状态
    public static void setPriorityStatus(boolean status) {
        priorityStatus = status;
    }
}
